In computer science, a ternary search tree is a special trie data structure where the child nodes of a standard trie are ordered as a binary search tree. Searching for a string in a ternary search tree consists of a series of binary searches, one for each character in the string. The current character in the string is thereby compared to the character at the current node:
The figure below shows a ternary search tree with the strings "as", "at", "cup", "cute", "he", "i" and "us":
c
/ | \
a u h
| | | \
t t e u
/ / | / |
s p e i s
As with other trie data structures, each node in a ternary search tree represents a prefix of the stored strings. All strings in the middle subtree of a node start with that prefix.
Like a binary search tree, a ternary search tree can be balanced or unbalanced, depending on the order the strings are inserted into the tree. Searching for a string of length m in a balanced ternary search tree with n strings requires at most m + log2(n) character comparisons. Roughly speaking, each comparison either consumes one character of the string or cuts the search space in half.
A compressed ternary search tree is a space-efficient variant where redundant nodes are removed. For example, in the figure above, the character sequences "cu", "te", "he" and "us" can be each compressed into one node. The number of nodes in such a tree is less than twice the number of strings. For each string, at most one new node is added and at most one existing node is split into two nodes.
|
||||||||||||||||||||||||||